//
//  17_电话号码的字母组合.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/14.
/**
 https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

 示例 1：

 输入：digits = "23"
 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 示例 2：

 输入：digits = ""
 输出：[]
 示例 3：

 输入：digits = "2"
 输出：["a","b","c"]

 */

import UIKit

/// 排列组合的问题一般都用DFS做
class PhoneNums: NSObject {
    
    func QA() {
        print(letterCombinations("23"))
        
    }
    
    let charDict: [Character: [Character]] = [
        "2": ["a", "b", "c"],
        "3": ["d", "e", "f"],
        "4": ["g", "h", "i"],
        "5": ["j", "k", "l"],
        "6": ["m", "n", "o"],
        "7": ["q", "p", "r", "s"],
        "8": ["t", "u", "v"],
        "9": ["w", "x", "y", "z"],
    ]
    
    func letterCombinations(_ digits: String) -> [String] {
    
        let chars = Array(digits)
        if chars.count == 0 { return [] }
        var charArray: [Character] = Array(repeating: " ", count: chars.count)
        var result = [String]()
        dfs(0, &charArray, chars, &result)
        return result
    }
    func dfs(_ index: Int, _ charArray: inout [Character], _ chars: [Character], _ result: inout [String]) {
        if index == chars.count {
            let str = String(charArray)
            result.append(str)
            return
        }
        
        let char = chars[index] // 字符
        let charNums = charDict[char] ?? []
        for item in charNums {
            charArray[index] = item
            dfs(index + 1, &charArray, chars, &result)
        }
    }
    
}
